from typing import *


class Solution:

    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)  # 数组长度
        i = n - 1  # 从最后一个开始向前找 nums[i - 1] < nums[i]
        while i > 0 and nums[i - 1] >= nums[i]:
            i -= 1
        if i != 0:  # 说明整个数组不是单调的 /\
            k = i
            while k < n and nums[i - 1] < nums[k]:
                k += 1
            j = k - 1  # j位置是大于i-1位置最小的数
            nums[i - 1], nums[j] = nums[j], nums[i - 1]
        j = n - 1
        while i < j:  # 逆序[i,j]
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1


t = Solution()
case = [2, 3, 1]
t.nextPermutation(case)
print(case)
case = [3, 2, 1]
t.nextPermutation(case)
print(case)
case = [1, 3, 2]
t.nextPermutation(case)
print(case)
